package 简单.动态规划.背包;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个 下标从 0 开始 的整数数组 nums ，返回满足下述条件
 * 的 不同 四元组 (a, b, c, d) 的 数目 ：
 * <p>
 * nums[a] + nums[b] + nums[c] == nums[d] ，且
 * a < b < c < d
 *  
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/count-special-quadruplets
 */
public class 统计特殊四元组_1995 {

    public static void main(String[] args) {

        int[] nums = {28, 8, 49, 85, 37, 90, 20, 8};
        System.out.println(countQuadruplets3(nums));

    }

    /**
     * 不能排序，a,b,c代表的是索引，元素和索引是一一对应的！！！
     *
     * @param nums
     * @return
     */
    public static int countQuadruplets(int[] nums) {
        int count = 0;
        int length = nums.length;
        for (int a = 0; a < length; a++) {  //先确定a,b,c，然后再寻找符号条件的d
            for (int b = a + 1; b < length; b++) {
                for (int c = b + 1; c < length; c++) {
                    for (int d = c + 1; d < length; d++) {
                        if (nums[a] + nums[b] + nums[c] == nums[d]) {
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }

    /**
     * a,b,c是确定的，可以得到d的取值范围，c<d<n
     * 用哈希表存储(c,n)中数字的个数，算出a+b+c的和在哈希表中出现的个数
     *
     * @param nums
     * @return
     */
    public static int countQuadruplets2(int[] nums) {
        int count = 0;
        int length = nums.length;
        Map<Integer, Integer> dMap = new HashMap<>();
        for (int a = 0; a < length; a++) {  //先确定a,b,c，然后再寻找符号条件的d
            for (int b = a + 1; b < length; b++) {
                for (int c = b + 1; c < length; c++) {
                    dMap.clear();  //需要清空上一层存的元素
                    for (int d = c + 1; d < length; d++) {
                        dMap.put(nums[d], dMap.getOrDefault(nums[d], 0) + 1);
                    }
                    count += dMap.getOrDefault(nums[a] + nums[b] + nums[c], 0);
                }
            }
        }
        return count;
    }

    /**
     * 使用上面的进行查询，反而增加了空间复杂度，并没有优化时间复杂度
     * 细节：
     * 在确定c时，可以进行逆序遍历，
     * 当c-1时，d的范围会+1
     * <p>
     * 2 ,3,5 2,4
     * *
     *
     * @param nums
     * @return
     */
    public static int countQuadruplets3(int[] nums) {
        int count = 0;
        Map<Integer, Integer> dMap = new HashMap<>();
        for (int c = nums.length - 2; c > 1; c--) {
            //把上一个元素放入d中，逆序是+1
            dMap.put(nums[c + 1], dMap.getOrDefault(nums[c + 1], 0) + 1);
            for (int a = 0; a < c; a++) {  //先确定c,确保a,可以取到除了c之外的所有元素
                for (int b = a + 1; b < c; b++) {  //确保可以取到除了a,c之外的所有元素
                    count += dMap.getOrDefault(nums[a] + nums[b] + nums[c], 0);
                }
            }
        }
        return count;
    }

    //TODO  多维背包？？？

}
